# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/15 上午9:11
    Author  : Thinkgamer
    File    : 605-种花问题.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/can-place-flowers/
"""

"""
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数n。能否在不打破种植规则的情况下种入n朵花？能则返回True，不能则返回False。

示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

注意:
数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

"""


"""
	思路 v1：
		从第一位开始判断，因为输入的数组是满足种植规则的，所以不会存在相邻的两个值都是1的情况
		所以只需要判断当前位和下一位是否为1，如果当前位为1，则跳跃到下两位，如果当前位不为1，下一位为1，则跳跃到第四位，否则该位置可以种花
	思路 v2：
		在序列的最前边和最后边各补一个0，然后判断连续0的个数，如果连续出现了三个0，则表示可以种植一棵花
	注意点：
		1、某位置可以种花之后 该位置应该赋值为1
		2、注意数组越界问题
		3、给定的值是小于等于可以最大种花数
"""


# 100ms 89.7% | 13.2 57.42%
def can_place_flowers_v1(flowerbed, n):
	count = 0
	i = 0
	while i < len(flowerbed):
		if flowerbed[i] == 1:
			i += 2
		elif i + 1 < len(flowerbed) and flowerbed[i + 1] == 1:
			i += 3
		else:
			count += 1
			flowerbed[i] = 1
			i += 2
	if count >= n:
		return True
	else:
		return False


# 36 ms 96.75% | 13.8m 8.97%
def can_place_flowers_v2(flowerbed, n):
	new_flowerbed = [0] + flowerbed + [0]
	count = 0
	for i in range(1, len(new_flowerbed)-1):
		if new_flowerbed[i-1] == 0 and new_flowerbed[i] == 0 and new_flowerbed[i+1] == 0:
			count += 1
			new_flowerbed[i] = 1

	return count >= n


# flowerbed = [1, 0, 0, 0, 1]
# flowerbed = [0, 1, 0]
# flowerbed = [0, 1, 0, 0, 1]
flowerbed = [1, 0, 0, 0, 0, 1]
# flowerbed = [1, 0, 0, 0, 1, 0, 0]
# flowerbed = [0, 0, 1, 0, 0]
n = 2
result = can_place_flowers_v2(flowerbed, n)
print(result)
